/*
 *    binary_tree.hpp (WordTrending)
 *    Asif Shahidullah
 *
 *    Implements the templated base binary tree object utilized
 *    by the trending project.
 *
 *    The pointer value of "0" should be replaced with nullptr
 *    if we are building with a C++11 complient compiler.
 *
 *    Note, the extension of this file is "hpp". This implies that
 *    all code associated with binary_tree exists here. See README
 *    Development Notes: 14 for the reason.
 *
 */

// non-standard include guard
#pragma once

// code partitioning
namespace ece { namespace tree {
   template <typename E>
   class binary_tree {
   public:
      class tree_data {
      public:
         E data;
         unsigned int frequency;
         unsigned int rank;
         bool tie;
         tree_data () { }
         tree_data (const E& data, unsigned int frequency) :
            data(data), frequency(frequency), rank(0), tie(false) { }

         tree_data& operator= (const tree_data& right) {
            this->data = right.data;
            this->frequency = right.frequency;
            return *this;
         }

         // Overloaded operator for mergesort comparisons
         bool operator>= (const tree_data& right) const {
            return (this->frequency >= right.frequency);
         }
      };
      binary_tree() : root(0), size_(0) { }
      binary_tree(const E& data) :
         root(new tree_node(data, 0)), size_(1) { }
      ~binary_tree() { }
      unsigned int size() { return size_; }
      void insert (const E& data);
      unsigned int lookup (const E& data);
      void remove(const E& data);
      void to_array (tree_data tree_array[]);
   private:
      enum child_type {
         left = 0,
         right,
         none
      };
      class tree_node {
      public:
         E data;
         unsigned int frequency;
         tree_node* left;
         tree_node* right;
         tree_node* parent;
         tree_node (const E& d, tree_node* p) :
            data(d), frequency(1), left(0), right(0), parent(p) { };
      };
      tree_node* root;
      unsigned int size_;
      void collision(tree_node* node) { ++node->frequency; }
      tree_node* get_node (const E& data);
   };
}}



/* Define scope resolution so we can write less headache- 
   inducing code. */
using namespace ece::tree;

template <typename E>
/* Iteratively traverse the tree locating the correct
   position to place a new key. */
void binary_tree<E>::insert(const E& data)
{
   enum child_type parent_linkage = none;
   tree_node* n = root,* parent = 0;

   // traverse the tree
   while (n != 0) {
      parent = n;
      if (data < n->data) {
         parent_linkage = left;
         n = n->left;
      } else if (data > n->data) {
         parent_linkage = right;
         n = n->right;
      } else
         return collision(n);
   }

   n = new tree_node (data, parent);

   // ensure correct parent-child linkage
   switch (parent_linkage) {
   case left:
      parent->left = n;
      break;
   case right:
      parent->right = n;
      break;
   case none:
   default:
      root = n;
      break;
   }
   
   ++size_;
}

template <typename E>
/* Search the binary tree for a specific key, returning
   the frequency associated with it */
unsigned int binary_tree<E>::lookup (const E& data) 
{
   tree_node* n;

   n = root;

   while (n != 0) {
      if (data < n->data)
         n = n->left;
      else if (data > n->data)
         n = n->right;
      else
         return n->frequency;
   }

   return 0;
}

template <typename E>
/* Returns the tree_node object associated with a 
   given E data value. */
typename binary_tree<E>::tree_node* binary_tree<E>::get_node (const E& data)
{
   tree_node* n;

   n = root;

   while (n != 0) {
      if (data < n->data)
         n = n->left;
      else if (data > n->data)
         n = n->right;
      else
         return n;
   }

   return 0;
}

template <typename E>
/* Removes a node from the tree */
void binary_tree<E>::remove (const E& data)
{
   tree_node re, min;

   if (lookup (data) == 0)
       return;

   // Get re node
   re = get_node (data);

   data = re->data;

   /* Removal of a leaf node */
   if (re->left == 0 && re->right == 0) {
       /* Update parent pointer */
       if (re->parent->left == re)
           re->parent->left = 0;
       else
           re->parent->right = 0;
       delete re;
   } 
   /* With a left subtree but no right subtree - replace node 
    * with left subtree */
   else if (re->left != 0 && re->right == 0) {
       if (re->parent->left == re)
           re->parent->left = re->left;
       else
           re->parent->right = re->left;
       delete re;
   }
   /* With a right subtree but no left subtree - replace node
    * with right subtree */
   else if (re->left == 0 && re->right != 0) {
       if (re->parent->left == re)
           re->parent->left = re->right;
       else
           re->parent->right = re->right;
       delete re;
   }
   /* Both left and right subtree */
   else {
       /* Find the minimum in the right subtree */
       min = re->right;
       while (min != 0)
           min = min->left;
       /* Swap data */
       re->data = min->data;
       /* Check to see if min has a right subtree, replace min
        * with it if that is the case, otherwise just free */
       if (min->right != 0)
           min->parent->left = min->right;
       else
           min->parent->left = 0;
       delete min;
   }
}

template <typename E>
/* Construct an array (of type tree_data) of all the 
   values in the binary tree via a post-order traversal, 
   removing all the data from the tree. This implies that
   this method should NOT be called until all binary tree
   has been fully populated.*/
void binary_tree<E>::to_array (tree_data tree_array[])
{
   unsigned int index = 0;
   tree_node* n = root,* parent = 0;

   /* Memory needs to be allocated outside of this function
      otherwise it's just recouped once this function returns */
   //tree_array = new tree_data[size_];

   if (n->left != 0)
      n = n->left;
   else if (n->right != 0)
      n = n->right;

   while (n != 0) {
      if (n->left != 0)
         n = n->left;
      else if (n->right != 0)
         n = n->right;
      else {
         parent = n->parent;

         tree_array[index++] = tree_data(n->data, 
            n->frequency);

         
         if (parent == 0) {
            delete n;
            return;
         }

         if (n == parent->left)
            parent->left = 0;
         else if (n == parent->right)
            parent->right = 0;

         delete n;

         n = parent;
      }
   }
}
